package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.util.*;
import java.util.concurrent.atomic.AtomicReference;

/**
 * 电台问题:使用贪心算法解决
 */
public class BroadcastProblem {
	@Test
	public void test1(){
		//创建每个电台
		Set<String> k1 = new HashSet<String>(){{add("北京");add("上海");add("天津");}};
		Set<String> k2 = new HashSet<String>(){{add("北京");add("广州");add("深圳");}};
		Set<String> k3 = new HashSet<String>(){{add("成都");add("上海");add("杭州");}};
		Set<String> k4 = new HashSet<String>(){{add("上海");add("天津");}};
		Set<String> k5 = new HashSet<String>(){{add("杭州");add("大连");}};
		//初始化数据,broads为电台map集合
		Map<String, Set<String>> broads = new HashMap<String, Set<String>>(){{put("K1",k1);put("K2",k2);put("K3",k3);put("K4",k4);put("K5",k5);}};
		//创建一个被选中的集合
		List<String> selects = new ArrayList<>();
		//创建一个所有未被覆盖的城市集合,并初始化数据
		Set<String> noFuGai = new HashSet<String>(){{
			broads.forEach((a,b) -> b.forEach(s -> add(s)));
		}};
		//定义一个指向最大覆盖城市电台的标识
		AtomicReference<String> maxBorad = new AtomicReference<>();
		//while循环,当未被覆盖的城市集合为空时结束循环
		while (!noFuGai.isEmpty()){
			maxBorad.set(null);
			//还有未被覆盖的城市时,循环broads集合,取出每个电台跟未被覆盖的城市进行验证,取共同集合
			broads.forEach((String a, Set<String> b) -> {
				//retainAll方法是将b和noFuGai集合中的共有数据放入b集合中
				b.retainAll(noFuGai);
				//当b集合中没有数据时,不进行验证
				if (b.size() != 0) {
					//判断,当最大电台标识为空或者当前遍历到的电台覆盖城市范围比前面得到的电台覆盖范围更大时,重新赋值覆盖范围最大的电台
					if (maxBorad.get() == null || b.size() > broads.get(maxBorad.get()).size()) {
						maxBorad.set(a);
					}
				}
			});
			//将选中的覆盖最大的电台放入选中集合
			selects.add(maxBorad.get());
			//将已覆盖的城市从未覆盖的城市中删除
			noFuGai.removeAll(broads.get(maxBorad.get()));
			//将电台中以甄别的数据删除
			broads.remove(maxBorad.get());
		}
		System.out.println(selects);
	}
}
